package com.linyaonan.leetcode.medium._143;

import java.util.ArrayList;

/**
 * 给定一个单链表 L 的头节点 head ，单链表 L 表示为：
 * <p>
 * L0 → L1 → … → Ln - 1 → Ln
 * 请将其重新排列后变为：
 * <p>
 * L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
 * 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/reorder-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class Solution {
    /**
     * 解法一：重新创建一个链表，赋值给head，不可以的，题目会直接判断原有链表
     *
     * @param head
     */
    public void reorderList(ListNode head) {
        ArrayList<Integer> list = new ArrayList<>();
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }

        ListNode start = new ListNode(-1);
        ListNode result = start;
        int l = 0;
        int r = list.size() - 1;

        while (l < r) {
            start.next = new ListNode(list.get(l));
            start = start.next;
            start.next = new ListNode(list.get(r));
            start = start.next;
            l++;
            r--;
        }
        // 奇数
        if ((list.size() & 1) == 1) {
            start.next = new ListNode(list.get(l));
        }

        head = result.next;

        System.out.println(head);
    }

    public void l2(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }
        //1.使用快慢指针分割链表,并记录后半段链表的头结点,此时是cur
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode cur = slow.next;
        slow.next = null;
        //2.将后半段链表进行翻转,翻转后头结点是pre
        ListNode pre = null;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        //3.将后半段链表挨个插入前半段链表中
        ListNode temp = head;
        while (pre != null && temp != null) {
            //3.1插入链表
            ListNode next1 = temp.next;
            ListNode next2 = pre.next;
            temp.next = pre;
            pre.next = next1;
            //3.2往后移动
            temp = next1;
            pre = next2;
        }
    }
}